#include <iostream>
#include <assert.h>
using namespace std;

namespace key
{
    template<class K>
    struct BSTNode
    {
        K _key;
        BSTNode<K>* _left;
        BSTNode<K>* _right;
        //构造
        BSTNode(const K& key)
            :_key(key)
            ,_left(nullptr)
            ,_right(nullptr)
        {}
    };
    template<class K>
    class BSTree
    {
        typedef BSTNode<K> Node;
    public:
        //插入
        bool Insert(const K& key)
        {
            if(_root == nullptr)
            {
                _root = new Node(key);
                return true;
            }
            Node* cur = _root;
            Node* parent = nullptr;
            while(cur)
            {
                if(cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if(cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return false;
                }
            }
            cur = new Node(key);
            if(parent->_key > key)
            {
                parent->_left = cur;
            }
            else if(parent->_key < key)
            {
                parent->_right = cur;
            }
            return true;
        }
        //查找
        bool find(const K& key)
        {
            Node* cur = _root;
            while(cur)
            {
                if(cur->_key > key)
                {
                    cur = cur->_left;
                }
                else if(cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if(cur->_key == key)
                {
                    return true;
                }
            }
            return false;
        }
        bool Erase(const K& key)
        {
            Node* cur = _root;
            Node* parent = nullptr;
            while(cur)
            {
                if(cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if(cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    //删除操作
                    if(cur->_left == nullptr)
                    {
                        //父亲指向我的右
                        if(cur == _root)
                        {
                            _root = _root->_right;
                        }
                        else
                        {
                            if(parent->_left == cur)
                            {
                                parent->_left = cur->_right;
                            }
                            else if(parent->_right == cur)
                            {
                                parent->_right = cur->_right;
                            }
                        }
                        delete cur;
                    }
                    else if(cur->_right == nullptr)
                    {
                        //父亲指向我的左
                        if(cur == _root)
                        {
                            _root = _root->_left;
                        }
                        else
                        {
                            if(parent->_left == cur)
                            {
                                parent->_left = cur->_left;
                            }
                            else if(parent->_right == cur)
                            {
                                parent->_right = cur->_left;
                            }
                        }
                        delete cur;
                    }
                    else
                    {
                        //找右子树最小(最左)结点替代法删
                        Node* minRightParent = cur;
                        Node* minRight = cur->_right;
                        while(minRight->_left)
                        {
                            minRightParent = minRight;
                            minRight = minRight->_left;
                        }
                        //覆盖
                        cur->_key = minRight->_key;
                        if(minRightParent->_left == minRight)
                            minRightParent->_left = minRight->_right;
                        else
                            minRightParent->_right = minRight->_right;
                        delete minRight;

                    }
                    return true;
                }
            }
            return false;
        }
        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }
    private:
        void _InOrder(Node* root)
        {
            if(root == nullptr)
            {
                return;
            }
            _InOrder(root->_left);
            cout << root->_key << " ";
            _InOrder(root->_right);
        }
        Node* _root = nullptr;
    };
}

namespace key_value
{
    template<class K,class V>
    struct BSTNode
    {
        K _key;
        V _val;
        BSTNode<K,V>* _left;
        BSTNode<K,V>* _right;
        BSTNode(const K& key,const V& val)
            :_key(key)
            ,_val(val)
            ,_left(nullptr)
            ,_right(nullptr)
        {}
    };
    template<class K,class V>
    class BSTree
    {
        typedef BSTNode<K,V> Node;
    public:
        //插入
        bool Insert(const K& key,const V& val)
        {
            if(_root == nullptr)
            {
                _root = new Node(key,val);
                return true;
            }
            Node* parent = nullptr;
            Node* cur = _root;
            while(cur)
            {
                if(cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if(cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if(cur->_key == key)
                {
                    return false;
                }
            }
            cur = new Node(key,val);
            if(parent->_key > key)
            {
                parent->_left = cur;
            }
            else if(parent->_key < key)
            {
                parent->_right = cur;
            }
            return true;
        }
        Node* Find(const K& key)
        {
            Node* cur = _root;
            while(cur)
            {
                if(cur->_key > key)
                {
                    cur = cur->_left;
                }
                else if(cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if(cur->_key == key)
                {
                    return cur;
                }
            }
            return nullptr;
        }
        bool Erase(const K& key)
        {
            Node* parent = nullptr;
            Node* cur = _root;
            while(cur)
            {
                if(cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if(cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if(cur->_key == key)
                {
                    //删除结点
                    if(cur->_left == nullptr)
                    {
                        if(cur == _root)
                        {
                            _root = _root->_right;
                        }
                        else
                        {
                            if(parent->_left == cur)
                            {
                                parent->_left = cur->_right;
                            }
                            else if(parent->_right == cur)
                            {
                                parent->_right = cur->_right;
                            }
                        }
                        delete cur;
                    }
                    else if(cur->_right == nullptr)
                    {
                        if(cur == _root)
                        {
                            _root = _root->_left;
                        }
                        else
                        {
                            if(parent->_left == cur)
                            {
                                parent->_left = cur->_left;
                            }
                            else if(parent->_right == cur)
                            {
                                parent->_right = cur->_left;
                            }
                        }
                        delete cur;
                    }
                    else
                    {
                        //找左子树最小的替换当前结点
                        Node* minRight = cur->_right;
                        Node* minRightParent = cur;
                        while(minRight->_left)
                        {
                            minRightParent = minRight;
                            minRight = minRight->_left;
                        }
                        //覆盖/交换,key/val结构的话key和val都要交换
                        cur->_key = minRight->_key;
                        cur->_val = minRight->_val;
                        //链接
                        if(minRightParent->_left == minRight)
                            minRightParent->_left = minRight->_right;
                        else if(minRightParent->_right == minRight)
                            minRightParent->_right = minRight->_right;
                        delete minRight;
                    }
                    return true;
                }
            }
            return false;
        }
        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }
    private:
        void _InOrder(Node* root)
        {
            if(root == nullptr) return;
            _InOrder(root->_left);
            cout << root->_key<< ":" << root->_val << " ";
            _InOrder(root->_right);
        }
        Node* _root = nullptr;
    };
}